//有两个水壶，容量分别为 jug1Capacity 和 jug2Capacity 升。水的供应是无限的。确定是否有可能使用这两个壶准确得到 
//targetCapacity 升。 
//
// 如果可以得到 targetCapacity 升水，最后请用以上水壶中的一或两个来盛放取得的 targetCapacity 升水。 
//
// 你可以： 
//
// 
// 装满任意一个水壶 
// 清空任意一个水壶 
// 从一个水壶向另外一个水壶倒水，直到装满或者倒空 
// 
//
// 
//
// 示例 1: 
//
// 
//输入: jug1Capacity = 3, jug2Capacity = 5, targetCapacity = 4
//输出: true
//解释：来自著名的 "Die Hard" 
//
// 示例 2: 
//
// 
//输入: jug1Capacity = 2, jug2Capacity = 6, targetCapacity = 5
//输出: false
// 
//
// 示例 3: 
//
// 
//输入: jug1Capacity = 1, jug2Capacity = 2, targetCapacity = 3
//输出: true
// 
//
// 
//
// 提示: 
//
// 
// 1 <= jug1Capacity, jug2Capacity, targetCapacity <= 10⁶ 
// 
// Related Topics深度优先搜索 | 广度优先搜索 | 数学 
//
// 👍 391, 👎 0 
//
//
//
//

package leetcode.editor.cn;

import java.util.*;

class WaterAndJugProblem {
    public static void main(String[] args) {
        Solution solution = new WaterAndJugProblem().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        // https://leetcode.cn/problems/water-and-jug-problem/solution/shui-hu-wen-ti-by-leetcode-solution/
        public boolean canMeasureWater(int jug1Capacity, int jug2Capacity, int targetCapacity) {
            // 左边装满，右边0
            // 左边0，右边装满
            // 左边清空
            // 右边清空
            // 左边倒入右边
            // 右边倒入左边

            // 根据上边状态，通过dfs来递归搜索，递归函数会超时，使用栈来模拟
            Stack<int[]> stack = new Stack<>();
            Set<Long> set = new HashSet<>();
            stack.push(new int[]{0, 0});
            while (!stack.isEmpty()) {
                int[] cur = stack.pop();
                if (set.contains(hash(cur))) continue;
                set.add(hash(cur));

                // 满足条件
                if (cur[0] == targetCapacity || cur[1] == targetCapacity || cur[0] + cur[1] == targetCapacity) return true;

                // dfs进行搜索
                stack.push(new int[]{jug1Capacity, cur[1]});
                stack.push(new int[]{cur[0], jug2Capacity});
                stack.push(new int[]{0, cur[1]});
                stack.push(new int[]{cur[0], 0});
                stack.push(new int[]{cur[0] - Math.min(cur[0], jug2Capacity - cur[1]), cur[1] + Math.min(cur[0], jug2Capacity - cur[1])});
                stack.push(new int[]{cur[0] + Math.min(cur[1], jug1Capacity - cur[0]), cur[1] - Math.min(cur[1], jug1Capacity - cur[0])});
            }

            return false;
        }

        public long hash(int[] state) {
            return (long) state[0] * 1000001 + state[1];
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
